public class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int low = 0;
        int high = len - 1;
        int mid;
        while(low < high) {
            mid = (low + high) / 2;
            if(nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if(nums[low] < target) {
            for(int i = low + 1; i < len; i++) {
                if(nums[i] > target) {
                    return i;
                }
            }
            return len;
        } else if(nums[low] > target) {
            for(int i = low - 1; i >= 0; i--) {
                if(nums[i] < target) {
                    return i + 1;
                }
            }
            return 0;
        } else {
            return low;
        }
    }
}